package com.hdu.other.dp.statusDP;

import java.util.Arrays;

public class lc464 {
    class Solution {
        public boolean canIWin(int n, int target) {
            int sum = (n * (n + 1)) / 2;
            if (sum < target) {
                return false;
            }
            if (n >= target) {
                return true;
            }
            // n = 4 -> 11111
            int status = (1 << (n + 1)) - 1;
            int[] dp = new int[1 << (n + 1)];
            Arrays.fill(dp, -1);
            return f(n, status, dp, target);
        }

        boolean f(int n, int status, int[] dp, int target) {
            if (target <= 0) {
                return false;
            }
            if (dp[status] != -1) {
                return dp[status] == 1;
            }
            boolean ans = false;
            for (int i = 1; i <= n; i++) {
                if ((status & (1 << i)) != 0 && (i >= target || !f(n, status ^ (1 << i), dp, target - i)))
                {
                    ans = true;
                    break;
                }
            }
            dp[status] = ans ? 1 : 0;
            return ans;
        }
    }
}
